<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    140. Word Break II
   </h1>
   <p>
    Given a
    <strong>
     non-empty
    </strong>
    string
    <em>
     s
    </em>
    and a dictionary
    <em>
     wordDict
    </em>
    containing a list of
    <strong>
     non-empty
    </strong>
    words, add spaces in
    <em>
     s
    </em>
    to construct a sentence where each word is a valid dictionary word.&nbsp;Return all such possible sentences.
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ul>
    <li>
     The same word in the dictionary may be reused multiple times in the segmentation.
    </li>
    <li>
     You may assume the dictionary does not contain duplicate words.
    </li>
   </ul>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:
</strong>s = "<code>catsanddog</code>"
wordDict = <code>["cat", "cats", "and", "sand", "dog"]</code>
<strong>Output:
</strong><code>[
&nbsp; "cats and dog",
&nbsp; "cat sand dog"
]</code>
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:
</strong>s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
<strong>Output:
</strong>[
&nbsp; "pine apple pen apple",
&nbsp; "pineapple pen apple",
&nbsp; "pine applepen apple"
]
<strong>Explanation:</strong> Note that you are allowed to reuse a dictionary word.
</pre>
   <p>
    <strong>
     Example 3:
    </strong>
   </p>
   <pre>
<strong>Input:
</strong>s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
<strong>Output:
</strong>[]</pre>
  </div>
  <div>
   <h1 class="question_title">
    140. 单词拆分 II
   </h1>
   <p>
    给定一个
    <strong>
     非空
    </strong>
    字符串
    <em>
     s
    </em>
    和一个包含
    <strong>
     非空
    </strong>
    单词列表的字典
    <em>
     wordDict
    </em>
    ，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
   </p>
   <p>
    <strong>
     说明：
    </strong>
   </p>
   <ul>
    <li>
     分隔时可以重复使用字典中的单词。
    </li>
    <li>
     你可以假设字典中没有重复的单词。
    </li>
   </ul>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <pre><strong>输入:
</strong>s = "<code>catsanddog</code>"
wordDict = <code>["cat", "cats", "and", "sand", "dog"]</code>
<strong>输出:
</strong><code>[
&nbsp; "cats and dog",
&nbsp; "cat sand dog"
]</code>
</pre>
   <p>
    <strong>
     示例 2：
    </strong>
   </p>
   <pre><strong>输入:
</strong>s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
<strong>输出:
</strong>[
&nbsp; "pine apple pen apple",
&nbsp; "pineapple pen apple",
&nbsp; "pine applepen apple"
]
<strong>解释:</strong> 注意你可以重复使用字典中的单词。
</pre>
   <p>
    <strong>
     示例&nbsp;3：
    </strong>
   </p>
   <pre><strong>输入:
</strong>s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
<strong>输出:
</strong>[]
</pre>
  </div>
 </body>
</html>